# -*- encoding: utf-8 -*-

"""
------------------------------------------
@File       : 7_quick_sort.py
@Author     : maixiaochai
@Email      : maixiaochai@outlook.com
@CreatedOn  : 2022/1/5 16:58
------------------------------------------
    快速排序，从小到大排序
    思路：
        1) 为了最大程度避免选择到最大/小值造成的时间复杂度为O(n^2)的最坏情况，可以随机选择一个元素作为基准元素，
            并且让基准元素和数列首元素交换位置，然后进行快速排序
        2) 为了简化步骤，这里省去了随机选择基准元素的过程，直接把首元素作为基准元素

    地位：快速排序算法与傅里叶变换等算法并称为二十世纪十大算法
"""


def quick_sort(start_index, end_index, array):
    """
        快速排序，双边循环
        递归结束条件: start_index ≥ end_index
    """
    if start_index >= end_index:
        return

    # 得到基准元素位置
    # pivot_index = partition_v1(start_index, end_index, array)
    pivot_index = partition_v2(start_index, end_index, array)

    # 根据基准元素分成两部分递归排序
    quick_sort(start_index, pivot_index - 1, array)
    quick_sort(pivot_index + 1, end_index, array)


def partition_v1(start_index, end_index, array):
    # 取第一个位置的元素作为基准元素（也可以选择随机位置）
    # 双边循环
    pivot = array[start_index]
    left = start_index
    right = end_index

    while left != right:
        # 控制right指针进行比较并左移
        # 因为从小到大排序，所以，pivot右边只留下比它大的元素，所以，> pivot: 左移，＜pivot：停止
        # 分支while中的 left  < right 很重要，如果不加这个限制，left和right有交叉的可能
        while left < right and array[right] > pivot:
            right -= 1

        # 控制left指针进行比较并右移，这里除了不等号 <，还有等号 =， 为了防止pivot和被指向的元素值相同的情况
        while left < right and array[left] <= pivot:
            left += 1

        if left < right:
            temp = array[left]
            array[left] = array[right]
            array[right] = temp

    # left = right时，pivot和重合点交换
    array[start_index] = array[left]
    array[left] = pivot
    return left


def partition_v2(start_index, end_index, array):
    """
    # 取第一个位置的元素作为基准元素（也可以选择随机位置）
    # 单边循环
    """
    # 取第一个元素作为基准元素
    pivot = array[start_index]
    mark = start_index

    for i in range(start_index + 1, end_index + 1):
        if array[i] < pivot:
            mark += 1
            temp = array[mark]
            array[mark] = array[i]
            array[i] = temp

    array[start_index] = array[mark]
    array[mark] = pivot
    return mark


def quick_sort_with_stack(start_index, end_index, array):
    """
        # 用一个集合栈来替代递归的函数栈
    """
    quick_sort_stack = []

    # 整个数列的起止下标，以哈希形式入栈
    root_param = {
        "start_index": start_index,
        "end_index": end_index
    }

    quick_sort_stack.append(root_param)

    # 循环结束条件：栈为空时结束
    while quick_sort_stack:
        # 栈顶元素出栈，得到起止下标
        param = quick_sort_stack.pop()

        # 得到基准元素位置
        pivot_index = partition_with_stack(param.get('start_index'), param.get("end_index"), array)

        # 根据基准元素分成两部分，把每一部分的起止下标入栈
        if param.get("start_index") < pivot_index - 1:
            left_param = {"start_index": root_param.get("start_index"), "end_index": pivot_index - 1}
            quick_sort_stack.append(left_param)

        if pivot_index + 1 < param.get("end_index"):
            right_param = {"start_index": pivot_index + 1, "end_index": param.get("end_index")}
            quick_sort_stack.append(right_param)


def partition_with_stack(start_index, end_index, array):
    """
        取第一个位置的元素作为基准元素（也可以随机位置）
    """
    pivot = array[start_index]
    mark = start_index

    for i in range(start_index + 1, end_index + 1):
        if array[i] < pivot:
            mark += 1
            temp = array[i]
            array[i] = array[mark]
            array[mark] = temp

    array[start_index] = array[mark]
    array[mark] = pivot
    return mark


def demo():
    my_array = [3, 4, 14, 1, 5, 6, 7, 8, 1, -1, 0, 9, 11]
    print(f"排序前：{my_array}")
    # quick_sort(0, len(my_array) - 1, my_array)
    quick_sort_with_stack(0, len(my_array) - 1, my_array)
    print(f"排序后：{my_array}")


if __name__ == '__main__':
    demo()
